# -*- coding:utf-8 -*-
from data_struct.single_link_list import ListLink

__author__ = 'gin.chen'


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# 迭代版本
class Solution(object):

    # def reverseList(self, head):
    #     """
    #     :type head: ListNode
    #     :rtype: ListNode
    #     """
    #     p = head
    #     pre = None
    #     while p is not None:
    #         tmp_node = p.next
    #         p.next = pre
    #         pre = p
    #         p = tmp_node
    #     return pre
    # 递归版本
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p


if __name__ == '__main__':
    pp = ListLink([1, 2, 3, 4, 5])
    pp.show()
    pp.set_heap(Solution().reverseList(pp.get_heap()))
    pp.show()
